package 课堂练习.Sort;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author yyz
 * @create 2023-12-05 15:51
 */
public class Sort {
    /**
     * 冒泡排序
     *
     * @param ints 待排序的数组
     */
    public void BulledSort(int[] ints) {
        boolean flag;
        for (int i = 0; i < ints.length; i++) {
            flag = false;
            for (int j = i + 1; j < ints.length; j++) {
                if (ints[i] > ints[j]) {
                    flag = true;
                    swap(ints, i, j);
                }
            }
            if (!flag) {
                return;
            }
        }
    }

    /**
     * 快速排序
     *
     * @param ints 待排序的数组
     */
    public void QuickSort(int[] ints) {
        quickSort(ints, 0, ints.length - 1);
    }

    /**
     * @param a     要排序的数组
     * @param left  左边界
     * @param right 右边界
     */
    private void quickSort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition2(a, left, right);
        quickSort(a, p + 1, right);
        quickSort(a, left, p - 1);
    }

    /**
     * 单边循环
     *
     * @param a     待排序的数组
     * @param left  左边界
     * @param right 右边界
     * @return
     */
    private int partition1(int[] a, int left, int right) {
        int i = left;//比基准值大的索引
        int j = left;//比基准值小的索引
        int t = a[right];
        while (j <= right) {
            while (a[j] < t) {
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
                j++;
            }
            j++;
        }
        swap(a, i, right);
        return i;
    }

    private int partition2(int[] a, int left, int right) {
        int x = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, x, left);
        int i = left + 1;//比基准值大的索引
        int j = right;//比基准值小的索引
        int t = a[left];
        while (i <= j) {
            while (i <= j && a[j] > t) {
                j--;
            }
            while (i <= j && a[i] <= t) {
                i++;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, j, left);
        return j;
    }

    /**
     * 交换数组位置
     *
     * @param a 数组
     * @param i 要交换的索引
     * @param j 要交换的索引
     */
    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 插入排序
     *
     * @param ints 待排序的数组
     */
    public void InsertionSort(int[] ints) {
        for (int j = 1; j < ints.length; j++) {
            int i = j - 1;
            int t = ints[j];
            while (i >= 0 && ints[i] > t) {
                ints[i + 1] = ints[i];
                i--;
            }
            if (i + 1 != j) {
                ints[i + 1] = t;
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param ints 待排序的数组
     */
    public void ShellSort(int[] ints) {
        for (int gap = ints.length >>> 1; gap >= 1; gap = gap >>> 1) {
            for (int j = gap; j < ints.length; j++) {
                int i = j - gap;
                int t = ints[j];
                while (i >= 0 && ints[i] > t) {
                    ints[i + gap] = ints[i];
                    i -= gap;
                }
                if (i + gap != j) {
                    ints[i + gap] = t;
                }
            }
        }
    }
}
